The present invention relates generally to a method and apparatus for decoding received symbols. More particularly, the present invention discloses a vector fix-lag algorithm for determining the probabilities of transmitted symbols given received symbols.
Forward-backward algorithms (FBAs) are often used in a variety of applications such as speech recognition, handwriting verification such as signature verification, error correction code decoding, etc., to calculate probabilities. As the name suggests, FBAs are a combination of forward algorithms and backward algorithms using vector-matrix products. Equipment that performs the algorithms requires large amounts of memory for storing all the matrices and intermediate matrix products needed to support the algorithms.
FBAs can be used to calculate the probabilities associated with the functions of Hidden Markov Models (HMMs) in voice recognition to recognize discrete and continuous speech. When a HMM is applied to describe a communication channel, products of sequences of probability density matrices are used to estimate the a posteriori probabilities of transmitted symbols given the received symbols. In other words, mathematical models are used to estimate the probabilities of the transmitted symbol knowing the received symbol.
Conventional FBA techniques require that a sequence of matrices multiplied by a first vector in a recursive manner in a forward part of the algorithm be stored in memory. The decoding process can start only after a long sequence of symbols has been received. This is unacceptable in many applications (a telephone application, for example) that impose strict constraints on the message delivery delay. Thus, new technology is needed to improve the vector-matrix product calculation that enables a decoder to estimate the product, and thus estimate the input symbols, without waiting for the whole symbol sequence to be received. This technology enables a designer to trade the product estimation accuracy for smaller delays in information delivery.
The invention provides a method and apparatus that performs a fixed-lag computation process.
The present invention discloses an apparatus and method of decoding information received over a noisy communications channel to determine the intended transmitted information. The present invention improves upon the traditional forward-backward algorithm with a vector fixed-lag algorithm. The algorithm is implemented by multiplying an initial state vector with a matrix containing information about the communications channel. The product is then recursively multiplied by the matrix xcfx84 times, using the new product with each recursive multiplication. The new product forward information is stored in storage elements. The final product is multiplied with a final state column vector yielding a probability of a possible input. The estimated input is the input having the largest probability. The invention may be applied to a maximum a posteriori estimation of input symbols in systems modeled by an input-output HMM such as symbols transmitted over noisy channels, to handwriting and speech recognition and other probabilistic systems.
The vector fixed-lag process of the invention replaces the conventional forward-backward algorithm. This eliminates the need of saving long sequences of the forward vectors. Accordingly, memory requirements and decoding delay are reduced when using the fixed-lag process to decode information transmitted over a communication channel.
The present invention discloses a fixed-lag method for determining the probability of a transmitted symbol at a time t, transmitted along a communications channel with bursts of errors, given a received symbol. The method comprises obtaining initial state information vector about the channel and obtaining channel information matrices describing the probabilities that the transmitted symbol would be transmitted along a communications channel with and without error. The method further comprises generating intermediate probabilities, each intermediate probability being the product of the initial state information vector at a time previous to time t, and a channel information matrix, storing the intermediate probabilities in storage elements, and multiplying a last intermediate probability with a final state vector to yield the probability of the transmitted symbol.